package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_797_所有可能的路径 {
    //测试
    public static void main(String[] args) {

//        System.out.println(new 力扣_797_所有可能的路径().allPathsSourceTarget(new int[][]{{1,2},{3},{3},{}}));
        System.out.println(new 力扣_797_所有可能的路径().allPathsSourceTarget(new int[][]{{4,3,1},{3,2,4},{3},{4},{}}));
    }

    /**
    题目：给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

      graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

     示例 1：
     输入：graph = [[1,2],[3],[3],[]]
     输出：[[0,1,3],[0,2,3]]
     解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

     示例 2：
     输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
     输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

    分析：【P 💙💙】
       1.深度递归--回溯法：队列记录前面的值，不断的深入寻找
                            记录当前遍历到第几个位置，已经进入到第几个数组
                            当值 == graph.length-1  时，跳出
                        --执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
    边界值 & 注意点：
       1.
     **/
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res =new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        path.add(0);
        dfs(graph,0,path,res);
        return res;
    }

    private void dfs(int[][] graph,int x, Deque<Integer> path, List<List<Integer>> res) {
        for (int i = 0; i < graph[x].length; i++) {
            if(graph[x][i]==graph.length-1){
                path.add(graph[x][i]);
                res.add(new ArrayList<>(path));
                path.pollLast();
            }else {
                path.add(graph[x][i]);
                dfs(graph,graph[x][i],path,res);
                path.pollLast();
            }
        }
    }
}
